UVa/10065 - Useless tile packers/10065.2.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4 #include <iterator>
   5 #include <cmath>
   6
   7 using namespace std;
   8
   9 struct point{
  10   int x,y;
  11   point() {}
  12   point(int X, int Y) : x(X), y(Y) {}
  13 };
  14
  15 point pivot;
  16
  17 ostream& operator<< (ostream& out, const point& c)
  18 {
  19   out << "(" << c.x << "," << c.y << ")";
  20   return out;
  21 }
  22
  23 //P es un polígono ordenado anticlockwise.
  24 //Si es clockwise, retorna el area negativa.
  25 //Si no esta ordenado retorna pura mierda.
  26 //P[0] != P[n-1]
  27 double area(const vector<point> &p){
  28   double r = 0.0;
  29   for (int i=0; i<p.size(); ++i){
  30     int j = (i+1) % p.size();
  31     r += p[i].x*p[j].y - p[j].x*p[i].y;
  32   }
  33   return r/2.0;
  34 }
  35
  36 //retorna si c esta a la izquierda de el segmento AB
  37 inline int cross(const point &a, const point &b, const point &c){
  38   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  39 }
  40
  41 //Self < that si esta a la derecha del segmento Pivot-That
  42 bool angleCmp(const point &self, const point &that){
  43   return( cross(pivot, that, self) < 0 );
  44 }
  45
  46 inline int distsqr(const point &a, const point &b){
  47   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  48 }
  49
  50 //vector p tiene los puntos ordenados anticlockwise
  51 vector<point> graham(vector<point> p){
  52   pivot = p[0];
  53   sort(p.begin(), p.end(), angleCmp);
  54   //Ordenar por ángulo y eliminar repetidos.
  55   //Si varios puntos tienen el mismo angulo se borran todos excepto el que esté más lejos
  56   for (int i=1; i<p.size()-1; ++i){
  57     if (cross(p[0], p[i], p[i+1]) == 0){ //Si son colineales...
  58       if (distsqr(p[0], p[i]) < distsqr(p[0], p[i+1])){ //Borrar el mas cercano
  59         p.erase(p.begin() + i);
  60       }else{
  61         p.erase(p.begin() + i + 1);
  62       }
  63       i--;
  64     }
  65   }
  66
  67   vector<point> chull(p.begin(), p.begin()+3);
  68
  69   //Ahora sí!!!
  70   for (int i=3; i<p.size(); ++i){
  71     while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) < 0){
  72       chull.erase(chull.end() - 1);
  73     }
  74     chull.push_back(p[i]);
  75   }
  76
  77   return chull;
  78 }
  79
  80 int main(){
  81   int n;
  82   int tileNo = 1;
  83   while (cin >> n && n){
  84     vector<point> p;
  85     point min(10000, 10000);
  86     int minPos;
  87     for (int i=0; i<n; ++i){
  88       int x, y;
  89       cin >> x >> y;
  90       p.push_back(point(x,y));
  91       if (y < min.y || (y == min.y && x < min.x )){
  92         min = point(x,y);
  93         minPos = i;
  94       }
  95     }
  96     double tileArea = fabs(area(p));
  97
  98     //Destruye el orden cw|ccw poligono, pero hay que hacerlo por que Graham necesita el pivote en p[0]
  99     swap(p[0], p[minPos]);
 100     pivot = p[0];
 101     double chullArea = fabs(area(graham(p)));
 102
 103     printf("Tile #%d\n", tileNo++);
 104     printf("Wasted Space = %.2f \%\n\n",  (chullArea - tileArea) * 100.0 / chullArea);
 105
 106   }
 107   return 0;
 108 }